<?php
/**
 * @title 1544. 整理字符串 - 栈+双指针
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param String $s
     * @return String
     */
    function makeGood($s) {
        /**
         * @since 2020-08-11 长度
         */
        $len = strlen($s);

        /**
         * @since 2020-08-11 左指针栈
         */
        $stacks = [];

        /**
         * @since 2020-08-11 双指针
         */
        $left = 0;
        $right = 1;

        /**
         * @since 2020-08-11 匹配
         */
        while($left <= $len-2){
            /**
             * @since 2020-08-11 大小写相同字符
             */
            if(abs(ord($s[$left]) - ord($s[$right])) == 32){
                /**
                 * @since 2020-08-11 删掉字符
                 */
                $s[$left] = " ";
                $s[$right] = " ";

                /**
                 * @since 2020-08-11 栈取左节点指针
                 */
                if(empty($stacks)){
                    $left = $right+1;
                    $right = $left+1;
                } else {
                    $left = array_pop($stacks);
                    $right++;
                }
            } else {
                /**
                 * @since 2020-08-11 left入栈
                 */
                $stacks[] = $left;

                /**
                 * @since 2020-08-11 右移1位
                 */
                $left = $right;
                $right = $left+1;
            }
        }

        /**
         * @since 2020-08-11 剔除空格
         */
        $s = str_replace(" ", "", $s);

        /**
         * @return
         */
        return $s;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.11_2.php
 */
$datas = [
    "leEeetcode",
    "abBAcC",
    "abBcCA",
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->makeGood($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
